package org.xqh.study.leetcode.algorithm;

import java.util.Arrays;

/**
 * @ClassName UnionFind
 * @Description 并查集
 * @Author xuqianghui
 * @Date 2021/2/14 22:25
 * @Version 1.0
 */
public class UnionFind {

    private int[] parent;

    private int[] size;//节点深度

    private int count;


    public UnionFind(int n) {
        this.count = n;
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        size = new int[n];
        Arrays.fill(size, 1);
    }

    public int getCount() {
        return count;
    }

    public int find(int idx){
        if(parent[idx] != idx){
            parent[idx] = find(parent[idx]);
        }
        return parent[idx];
    }

    public void union(int x, int y){
        //
        x = find(x);
        y = find(y);
        if(x == y){
            return ;
        }

        if(size[x] < size[y]){
            int tmp = x;
            x = y;
            y = tmp;
        }

        parent[y] = x;
        size[x] += size[y];
        count --;//连通分量 --
    }
}
